package com.wtgroup.demo.mianshi.算法.排序;

import java.util.Arrays;

/**
 * 面试推荐版本
 */
public class QuickSort1 {
    /*
    1. 枢纽元(基准值)选取策略. 错误做法是取第一个. (但这个简单, 应付面试应该OK).
    2. 等于枢纽元的, 怎么划分.
    3. 如果是两端往中间靠, 则枢纽元一定一定不能参与分割. 如 [9,5,6,5,1] , 枢纽元设为 5 => [1,5,6,5,9], 这就错了.
    [9,5,6,1, 5] -> [1,5,6,9, 5] -> 枢纽元和最后i位置互换 [1,5,_5_,9,6]


    @: 选第一个作为枢纽元, 分割时不含第一个. 这样可以随便怎么分割, 最后, 将枢纽元和所在位置互换.

    小于基准值的往前, 大于基准值的往后放.

    */

    public static void main(String[] args) {
        int[] arr = new int[] { 2, 3, 1, 5, 6, 5, 29 };

        quickSort2(arr, 0, arr.length-1);

        System.out.println(Arrays.toString(arr));
    }

    /**
     * 精简版
     *
     * 《算法导论》快速排序（CH7 P170）。
     * @param arr
     * @param left
     * @param right
     */
    public static void quickSort2(int[] arr, int left, int right) {
        // 分区: 根据枢纽元划分大小两部分, 返回临界索引, 然后递归
        if (left < right) {
            int center = partition(arr, left, right);
            quickSort2(arr, left, center - 1);
            quickSort2(arr, center + 1, right);
        }
    }

    /**right 作为枢纽元
     * @param arr
     * @param left
     * @param right
     * @return
     */
    private static int partition(int[] arr, int left, int right) {
        int pivot = arr[right];
        int sloti = left; // 下一次小值放的槽, 一旦发生了交换, 后移一位, 共下次使用
        for (int i = left; i < right; i++) {
            // 2023-5-1 10:51:11 貌似 是否含'=' 无所谓
            if (arr[i] <= pivot) { // 含=，否则可能导致等于枢纽元的夹在大于的后面 (似乎不影响, 即使在大的后面, 下次, 下下次, 总会被调换到枢纽元挨着)
                SortUtil.swap(arr, i, sloti);
                sloti++;
            }
        }
        SortUtil.swap(arr, sloti, right);
        return sloti;
    }


    /**
     * 第一个元素作为枢纽元
     * @link https://www.cnblogs.com/onepixel/articles/7674659.html
     * @param arr
     * @param left
     * @param right
     */
    public static void quickSort(int[] arr, int left, int right) {
        if(right<=left) {
            return;
        }

        int pivot = arr[left];
        int k = left+1;
        for (int i = k; i < arr.length; i++) {
            if(arr[i] < pivot) {
                SortUtil.swap(arr, i, k);
                k++;
            }
        }

        SortUtil.swap(arr, k-1, left);

        quickSort(arr, left, k-2);
        quickSort(arr, k, right);
    }

}
